__all__ = ['merge_sort', 'merge_sort_linkqueue']

from algo.data_structure import LinkedQueue


def merge(sub_arr_1, sub_arr_2, array):
    i = j = 0
    while i + j < len(array):
        if j == len(sub_arr_2) or (i < len(sub_arr_1) and sub_arr_1[i] < sub_arr_2[j]):
            array[j + i] = sub_arr_1[i]  # copy sub_arr_1的第i个元素作为array的下一个元素
            i += 1
        else:
            array[i + j] = sub_arr_2[j]  # copy sub_arr_2的第j个元素作为array的下一个元素
            j += 1


def merge_sort(array:list):
    """
    基于数组的归并排序
    :param array:
    :return:
    """
    n = len(array)
    if n < 2:
        return
    # 划分子区域
    mid = n //2
    sub_arr_1 = array[0:mid]
    sub_arr_2 = array[mid:n]
    merge_sort(sub_arr_1)
    merge_sort(sub_arr_2)
    # 合并
    merge(sub_arr_1, sub_arr_2, array)


def merge_linkqueue(sub_lq_1:LinkedQueue, sub_lq_2:LinkedQueue, lq:LinkedQueue):
    while not sub_lq_1.is_empty() and not sub_lq_2.is_empty():
        if sub_lq_1.first() < sub_lq_2.first():
            lq.enqueue(sub_lq_1.dequeue())
        else:
            lq.enqueue(sub_lq_2.dequeue())

    while not sub_lq_1.is_empty():
        lq.enqueue(sub_lq_1.dequeue())
    while not sub_lq_2.is_empty():
        lq.enqueue(sub_lq_2.dequeue())


def merge_sort_linkqueue(lq:LinkedQueue):
    """
    基于链表队列的归并排序
    :param lq:
    :return:
    """
    n = len(lq)
    if n < 2:
        return

    # 划分子区域
    sub_lq_1 = LinkedQueue()
    sub_lq_2 = LinkedQueue()
    while len(sub_lq_1) < n //2:
        sub_lq_1.enqueue(lq.dequeue())
    while not lq.is_empty():
        sub_lq_2.enqueue(lq.dequeue())

    merge_sort_linkqueue(sub_lq_1)
    merge_sort_linkqueue(sub_lq_2)
    merge_linkqueue(sub_lq_1, sub_lq_2, lq)